package leetcode.code1284;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	// 四方遍历数组，{左，右，上，下}
	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };

	public int minFlips(int[][] mat) {
		int m = mat.length, n = mat[0].length;
		int num = m * n;
		List<Integer>[] ways = this.ways(m, n);
		boolean[] been = new boolean[1 << num];
		int stat = 0;// 初始状态
		int[][] indexs = new int[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int cur = mat[i][j];
				int index = this.index(i, j, n);
				if (cur == 1) {
					stat |= (1 << index);
				}
				indexs[i][j] = index;
			}
		}
		if (stat == 0) {
			return 0;
		}
		Queue<int[]> queue = new LinkedList<>();
		been[stat] = true;
		queue.add(new int[] { stat, 0 });// 初始状态需要0次
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			int curStat = cur[0], dist = cur[1];
			int nextDist = dist + 1;
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					int index = this.index(i, j, n);
					List<Integer> way = ways[index];
					int nextStat = this.change(curStat, index, way);
					if (nextStat == 0) {// 达到翻转目标
						return nextDist;
					}
					if (!been[nextStat]) {
						been[nextStat] = true;
						queue.add(new int[] { nextStat, nextDist });
					}
				}
			}
		}
		return -1;
	}

	// 在状态curStat时，翻转index和邻接way的位置
	public int change(int curStat, int index, List<Integer> way) {
		curStat = opposite(curStat, index);
		for (int around : way) {
			curStat = opposite(curStat, around);
		}
		return curStat;
	}

	// num中index位1,0互换
	public int opposite(int num, int index) {
		int pos = 1 << index;
		if ((num & pos) == 0) {
			return num + pos;
		} else {
			return num - pos;
		}
	}

	// 二维转一维
	public int index(int i, int j, int n) {
		return i * n + j;
	}

	// 邻接位置表
	public List<Integer>[] ways(int m, int n) {
		int len = m * n;
		List<Integer>[] ways = new ArrayList[len];
		for (int i = 0; i < len; i++) {
			ways[i] = new ArrayList<>();
		}
		for (int x = 0; x < m; x++) {
			for (int y = 0; y < n; y++) {
				int index = index(x, y, n);
				for (int i = 0; i < 8; i += 2) {
					int nextx = x + d[i], nexty = y + d[i + 1];
					if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
						int nextIndex = index(nextx, nexty, n);
						ways[index].add(nextIndex);
					}
				}
			}
		}
		return ways;
	}

	@Override
	public void debug4() {
		HelpDebug.compare(-1, this.minFlips(HelpDebug.str2array1("[[1,0,0],[1,0,0]]")));
		HelpDebug.compare(0, this.minFlips(HelpDebug.str2array1("[[0]]")));
		HelpDebug.compare(3, this.minFlips(HelpDebug.str2array1("[[0,0],[0,1]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
